<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>Numbers WIthout Consecutive 1s in binary representation</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="numbers-without-consecutive-1s-in-binary-representation">Numbers WIthout Consecutive 1s in binary representation</h1>
<ul>
<li><a href="https://www.youtube.com/watch?v=a9-NtLIs1Kk&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=39">https://www.youtube.com/watch?v=a9-NtLIs1Kk&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=39</a></li>
</ul>
<p>查找0 ~ 2^n 之间的所有数的二进制形式，如果不存在连续的1， 则是符合题意的&quot;Numbers WIthout Consecutive 1s in binary representation&quot;</p>
<p>这样的数目有多少个？  关键是证明数目符合斐波拉切数列。 以 n=4为例，可以分为两部分</p>
<ol>
<li>第一列是0， 符合条件的数目和n=3情况相同</li>
<li>第一列是1， 如何条件的数目和n=2情况相同</li>
</ol>
<p>所以 f(4) = f(3) + f(2) = 5 + 3 = 8</p>
<p><img src="file:///e:\gitee\leetcode\math\pics\dp17.png" alt="dp17.png"></p>

    </body>
    </html>